The Internet is a general purpose, public computer network which allows millions of computers all over the world, connected to the Internet, to communicate and exchange digital data with other computers also coupled to the Internet. As new technologies emerge, the speed at which one can connect onto the Internet is ever increasing. Now, users on the Internet have the bandwidth to participate in live discussions in chat rooms, play games in real-time, watch streaming video, listen to music, shop and trade on-line, etc. In the future, it is imagined that the bandwidth will be such that video-on-demand, HDTV, IP telephony, video teleconferencing, and other types of bandwidth intensive applications will soon be possible.
One approach by which bandwidth is being increased relates to fiber optics technology. By sending pulses of light through glass fibers no thicker than a human hair, vast amounts of digital data can be transmitted at extremely high speeds. And with the advent of dense wavelength division multiplexing, different wavelengths of light can be channeled over the same, single fiber strand, thereby increasing its capacity several fold.
However, there is a problem with distributing the bandwidth of this new fiber optic network to end users. As is well known, some applications are insensitive to bandwidth constraints, such as latency and dropped packets. For example, email applications and basic Web browsing are relatively time insensitive to latency and dropped packets. On the other hand, applications such as real time two way voice communication or video are very sensitive to time delays caused by latency and dropped packets. Acceptable performance of these applications is highly dependent upon the provision of a guaranteed minimum bandwidth.
Unfortunately, due to network traffic congestion, network availability, routing conditions, and other uncontrollable external factors, the provisioning of a guaranteed level of bandwidth availability for certain customers has proven problematic. In general, data packets vie for available bandwidth and are routed according to a best-effort delivery model. As such, the reliability of traditional packet switched data networks is at times sub-optimal. For example, in most cases, it is very difficult to provide any kind of quality of service (QoS) using traditional LAN switches and routers on IP networks. QoS refers to the guarantee of providing timely delivery of information, controlling bandwidth per user, and setting priorities for select traffic.
Different network traffic flows (or simply “flows”) are respectively associated with different applications. A flow refers to the transmission of packets from a sender to a receiver to support an application, such as transferring a Web page, implementing a voice over IP conversation, playing a video, or the like. Some flows are described as real time flows since they require very low latency (e.g., a voice over IP application). Other flows are not so much latency dependent as they are consistent data transfer rate dependent (e.g., video over the Web). For real-time application flows such as video on demand, HDTV, voice communications, etc., dropped packets or late-arriving packets of the flows can seriously disrupt or even destroy performance. And for many Internet Service Providers (ISP's), Applications Service Providers (ASP's), web sites/portals, and businesses, it is of paramount importance that they have the ability to provide these flows with a certain minimum threshold bandwidth and/or latency. For example, an e-commerce or business web site may lose critical revenue from lost sales due to customers not being able to access their site during peak hours.
Because QoS is so highly desired by some users, there are mechanisms which have been developed to provide QoS functionality. One prior art method for implementing QoS is the use of various TDM (time division multiplexing) schemes. One widely used TDM scheme is the implementation of T-carrier services (e.g., T1 line for carrying data at 1.544 Mbits/sec. and T3 line for carrying data at a much faster rate of 274.176 Mbits/sec). These T1 and T3 lines are dedicated point-to-point datalinks leased out by the telephone companies. The telephone companies typically charge long distance rates (e.g., $1,500-$20,000 per month) for leasing out a plain old T1 line. Another commonly used TDM scheme for achieving QoS relates to Synchronous Optical Network (SONET). As with T-carrier services, SONET uses TDM to assign individual channels, or flows, to pre-determined time slots. With TDM, each channel is guaranteed its own specific time slot in which it can transmit its data. Although TDM enables QoS, it is costly to implement because both the transmitter and receiver must be synchronized at all times. The circuits and overhead associated with maintaining this precise synchronization is costly. Furthermore, TDM based networking technologies are inefficient with respect to unused time slots. If flows are inactive, their allocated bandwidth is wasted. In general, with TDM technologies, unused bandwidth from inactive flows is not reallocated to other users.
Another prior art method is the use of various forms of bandwidth reservations in conjunction with asynchronous schemes. Asynchronous data transmission schemes provide numerous advantages when compared to synchronous TDM type schemes, and as such, are generally overtaking synchronous technologies in both voice and data network installations (e.g., the IP based networks of the Internet). In implementing QoS, asynchronous schemes usually function by reserving a portion of their bandwidth for “high priority” latency sensitive flows. With most asynchronous schemes (e.g., Ethernet), QoS performance deteriorates with the increasing bandwidth utilization of the network. As the percentage of available bandwidth utilized by the network increases, the less efficient the prior art asynchronous QoS reservation schemes perform. Such schemes either maintain a large margin of unused bandwidth to ensure QoS, thereby virtually guaranteeing an under-utilization of available total bandwidth, or over-allocate bandwidth, leading to the abrupt dropping data for some users and/or ruining QoS for any high priority users.
Thus what is required is a solution that provides the advantages of asynchronous data networks while efficiently implementing QoS. What is required is a solution that enables the efficient allocation of available bandwidth, thereby allowing guaranteed QoS. The required solution should be able to allocate bandwidth to individual flows asynchronously without incurring the deteriorating performance of prior art asynchronous schemes with increasing scale (e.g., extremely large number of flows) and increasing network utilization. The required solution should be able to ensure a minimum amount of reserved bandwidth without incurring the wasted bandwidth problems of prior art TDM based networking schemes where bandwidth is wasted on inactive flows.
The required solution should be able to track individual flows on an individual basis, in order to ensure individual flows are not starved of bandwidth, while simultaneously ensuring bandwidth is not over-allocated to flows which do not require it. The required solution should be able to track when individual flows are active and when they are inactive, thereby allowing the bandwidth allocated to the inactive flows to be reassigned to those flows in need of it. The required solution should be capable of tracking total allocated bandwidth in real time, thereby allowing efficient allocation of unused bandwidth in real time while maintaining QoS. The real-time total allocated bandwidth tracking should allow the dynamic allocation of unused bandwidth in real-time. The present invention provides a novel solution to the above requirements.